package com.leetcode.程序员面试金典.hard;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author 覃国强
 * @date 2021-09-13 13:07
 */
public class 面试题_08_13_堆箱子 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] box = {{1, 1, 1}, {2, 3, 4}, {2, 6, 7}, {3, 4, 5}};
    int hi = solution.pileBox(box);
    System.out.println(hi);
  }

  static
  class Solution {
    public int pileBox(int[][] box) {

      if (box == null || box.length == 0) {
        return 0;
      }

      BoxObj[] boxObjs = new BoxObj[box.length];
      int index = 0;
      for (int[] e : box) {
        boxObjs[index++] = new BoxObj(e[0], e[1], e[2]);
      }

      Comparator<BoxObj> comparator = Comparator.comparingInt(BoxObj::getWi).reversed();
      Arrays.sort(boxObjs, comparator);

//      return getMaxHi(boxObjs, -1,0);
      return getMaxHi(boxObjs);
    }

    private int getMaxHi(BoxObj[] boxObjs) {
      int[] maxHis = new int[boxObjs.length];
      maxHis[0] = boxObjs[0].hi;

      int result = maxHis[0];

      for (int curIndex = 1; curIndex < boxObjs.length; ++curIndex) {
        // 以当前箱子作为最底部
        maxHis[curIndex] = boxObjs[curIndex].hi;
        for (int lastIndex = 0; lastIndex < curIndex; ++lastIndex) {
          if (isValid(boxObjs, lastIndex, curIndex)) {
            // 以 lastIndex 箱子作为当前箱子的底部
            maxHis[curIndex] = Math.max(maxHis[curIndex], maxHis[lastIndex] + boxObjs[curIndex].hi);
          }
        }
        result = Math.max(result, maxHis[curIndex]);
      }

      return result;
    }


    private int getMaxHi(BoxObj[] boxObjs, int lastIndex, int index) {
      if (index == boxObjs.length) {
        return 0;
      }

      int result1 = 0;

      if (isValid(boxObjs, lastIndex, index)) {
        // 取
        result1 = boxObjs[index].hi + getMaxHi(boxObjs, index, index + 1);
      }

      // 不取
      int result2 = getMaxHi(boxObjs, lastIndex, index + 1);

      return Math.max(result1, result2);
    }

    private boolean isValid(BoxObj[] boxObjs, int lastIndex, int index) {
      if (lastIndex == -1) {
        return true;
      }
      return boxObjs[lastIndex].wi > boxObjs[index].wi &&
          boxObjs[lastIndex].di > boxObjs[index].di &&
          boxObjs[lastIndex].hi > boxObjs[index].hi;
    }

    private static class BoxObj {
      int wi;
      int di;
      int hi;

      public BoxObj(int wi, int di, int hi) {
        this.wi = wi;
        this.di = di;
        this.hi = hi;
      }

      public int getWi() {
        return wi;
      }
    }
  }

}
